class Solution:
	# @param num, a list of integer
	# @return a list of lists of integer
	def subsetsWithDup(self, S):
		menu = {}
		for i in S:
			if i not in menu:
				menu[i] = 1
			else:
				menu[i] += 1
		items = sorted(menu.iteritems(), key = lambda e: e[0])
		ans = []
		self.__dfs(items, [0 for i in items], 0, ans)
		return ans

	def __dfs(self, items, mark, curr, ans):
		if curr == len(items):
			ans.append(self.__gen(items, mark))
			return
		for i in xrange(items[curr][1] + 1):
			mark[curr] = i
			self.__dfs(items, mark, curr+1, ans)



	def __gen(self, items, mark):
		ans = []
		for i in xrange(len(mark)):
			for j in xrange(mark[i]):
				ans.append(items[i][0])
		return ans

if __name__ == '__main__':
	so = Solution()
	a = [1,2,2,3]
	z = so.subsetsWithDup(a)
	print z